#include <iostream>
#include <numeric>
#include <vector>
// 堆是完全二叉树，可以使用数组来存储堆元素

template <typename T> class MaxHeap {
private:
  std::vector<T> _maxHeap;
  int _size;
  int left(int i) { return 2 * i + 1; }
  int right(int i) { return 2 * i + 2; }
  int parent(int i) { return (i - 1) / 2; }
  void swap(T &t1, T &t2) {
    T t = t1;
    t1 = t2;
    t2 = t;
  }

  void siftDown(int i) {
    while (true) {
      int l = left(i);
      int r = right(i);
      int ma = i;
      if (l < _size - 1 && _maxHeap[l] > _maxHeap[ma])
        ma = l;
      if (r < _size - 1 && _maxHeap[r] > _maxHeap[ma])
        ma = r;
      if (ma == i)
        break;
      swap(_maxHeap[i], _maxHeap[ma]);
      i = ma;
    }
  }

  //   void siftDown(int i) {
  //     while (true) {
  //       int l = left(i);
  //       int r = right(i);
  //       // 有叶子节点
  //       if (l < _size) {
  //         // 左右节点均存在
  //         if (r < _size) {
  //           // 左节点大于右节点
  //           if (_maxHeap[l] > _maxHeap[r]) {
  //             // 当前值比左节点小 交换当前值
  //             if (_maxHeap[i] < _maxHeap[l]) {
  //               swap(_maxHeap[i], _maxHeap[l]);
  //               i = l;
  //               continue;
  //             }
  //             // 当前值大于左节点 小于右节点
  //             if (_maxHeap[i] < _maxHeap[r]) {
  //               swap(_maxHeap[i], _maxHeap[r]);
  //               i = r;
  //               continue;
  //             }
  //             // 当前值比两个节点都大 不用交换 结束堆化
  //             return;
  //             // 右节点大于左节点
  //           } else {
  //             // 当前值比右节点小 交换当前值
  //             if (_maxHeap[i] < _maxHeap[r]) {
  //               swap(_maxHeap[i], _maxHeap[r]);
  //               i = r;
  //               continue;
  //             }
  //             // 当前值大于右节点 小于左节点
  //             if (_maxHeap[i] < _maxHeap[r]) {
  //               swap(_maxHeap[i], _maxHeap[l]);
  //               i = l;
  //               continue;
  //             }
  //             // 当前值比两个节点都大 不用交换 结束堆化
  //             return;
  //           }
  //         } else {
  //           // 只有左节点存在
  //           if (_maxHeap[l] > _maxHeap[i]) {
  //             swap(_maxHeap[l], _maxHeap[i]);
  //             i = l;
  //             continue;
  //           } else {
  //             // 大于它的单一子节点 堆化完成
  //             return;
  //           }
  //         }
  //       } else {
  //         // 无叶子节点直接退出
  //         return;
  //       }
  //     }
  //   }

public:
  MaxHeap() : _size(0) {}
  // 元素入堆
  void push(const T &t) {
    // 1.将元素放入堆底
    _maxHeap.push_back(t);
    // 当前位置
    int index = _size++;
    // 只有一个元素
    if (index == 0)
      return;
    // 与上一层元素比较
    while (index > 0) {
      int p = parent(index);
      if (_maxHeap[p] <= _maxHeap[index]) {
        swap(_maxHeap[p], _maxHeap[index]);
        index = p;
      } else {
        return;
      }
    }
  }
  // 对顶元素
  const T &peek() { return _maxHeap[0]; }

  // 弹出堆顶元素
  T pop() {
    // 1.拿到堆顶元素
    T t = _maxHeap[0];
    // 2.交换堆顶和堆底元素
    swap(_maxHeap[0], _maxHeap[--_size]);
    // 3.执行堆化操作
    siftDown(0);
    return t;
  }

  int size() { return _size; }
  bool empty() { return !(_size > 0); }
};

int main() {
  MaxHeap<int> maxHeap;
  maxHeap.push(2);
  std::cout << maxHeap.peek() << std::endl;
  maxHeap.push(3);
  std::cout << maxHeap.peek() << std::endl;
  maxHeap.push(4);
  std::cout << maxHeap.peek() << std::endl;
  maxHeap.push(5);
  std::cout << maxHeap.peek() << std::endl;
  maxHeap.push(6);
  std::cout << maxHeap.peek() << std::endl;
  maxHeap.push(7);
  std::cout << maxHeap.peek() << std::endl;

  while (!maxHeap.empty()) {
    std::cout << maxHeap.pop() << std::endl;
  }
  return 0;
}